package datasorters;

import org.apache.log4j.Logger;

public class MergeSort implements DataSorter<Integer> {
    private static final Logger l = Logger.getLogger(MergeSort.class);
    private static int[] auxiliary;
    private static int timeUsed = 0;

    private static void sortAsc(Integer[] data, int beginning, int end) {
        if (beginning >= end) {
            return;
        }
        int middle = beginning + (end - beginning) / 2;
        sortAsc(data, beginning, middle);
        sortAsc(data, middle + 1, end);
        merge(data, beginning, middle, end);
    }

    private static void merge(Integer[] data, int beginning, int middle, int end) {
        for (int k = beginning; k <= end; k++) {
            auxiliary[k] = data[k];
        }
        int i = beginning;
        int j = middle + 1;
        for (int k = beginning; k <= end; k++) {
            if (i > middle) {
                data[k] = auxiliary[j++];
            } else if (j > end) {
                data[k] = auxiliary[i++];
            } else if (auxiliary[j] < auxiliary[i]) {
                timeUsed++;
                data[k] = auxiliary[j++];
            } else {
                timeUsed++;
                data[k] = auxiliary[i++];
            }
        }
    }

    private static void reverse(Integer[] data) {
        for (int i = 0; i < data.length / 2; i++) {
            int temp = data[i];
            data[i] = data[data.length - 1 - i];
            data[data.length - 1 - i] = temp;
        }
    }

    public Integer[] sort(Integer[] data) {
        if (data == null)
            return null;
        if (data.length == 0)
            return data;

        Integer[] sortedData = new Integer[data.length];
        System.arraycopy(data, 0, sortedData, 0, data.length);
        auxiliary = new int[data.length];
        int memoryUsed = auxiliary.length;

        sortAsc(sortedData, 0, sortedData.length - 1);

        int expectedTime = (int) (data.length * (Math.log10(data.length) / Math.log10(2)));
        l.info("Time used: " + timeUsed + ". Expected time: NlgN = " + expectedTime);
        l.info("Memory used: " + memoryUsed + ". Expected memory: N = " + data.length);

        auxiliary = null;
        timeUsed = 0;

        return sortedData;
    }

    public Integer[] sort(Integer[] data, SortType type) {
        Integer[] sortedData = sort(data);
        if (SortType.DESC.equals(type))
            reverse(sortedData);
        return sortedData;
    }
}
